package com.yang.Offer;

import java.util.HashMap;
import java.util.Map;

public class Offer07 {
}
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

/*输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。
假设输入的前序遍历和中序遍历的结果中都不含重复的数字。*/
class Offer07Solution {
    private Map<Integer, Integer> map = new HashMap();
/*    public TreeNode buildTree(int[] preorder, int[] inorder) {
        // 通过前序遍历拿根节点
        // 通过根节点获取中序遍历的左右子树界限分割  //有中序遍历左子树[L2, i-1] [i+1, R2];
        //  通过中序遍历得到的区间 可以确前序遍历区间 左子树[L1, L1 + (i-L2)] 右子树 [L1+(i-L2+1) , R1]
        if(preorder == null || preorder.length <= 0){
            return null;
        }
        for(int i = 0; i < preorder.length; i++){
            map.put(inorder[i], i);
        }
        TreeNode root = f(preorder, 0, preorder.length - 1, 0, inorder.length - 1);
        return root;
    }

    private TreeNode f(int[] preorder, int l1, int r1, int l2, int r2){
        // 没有左右子树
        if(l1 > r1 && l2 > r2){
            return null;
        }
        TreeNode root = new TreeNode(preorder[l1]);
        // 获取根节点下标
        int i = map.get(preorder[l1]);
        root.left = f(preorder, l1 + 1, l1 + (i - l2), l2, i - 1);
        root.right = f(preorder, l1+(i+1-l2), r1, i + 1, r2);

        return root;
    }*/
}
